<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <!-- 让字符串成为回文串的最少插入次数 -->
    <script>
      var minInsertions = function (s) {
        const n = s.length
        const dp = new Array(n).fill(0).map(() => new Array(n).fill(0))
        for (let i = n - 2; i >= 0; i--) {
          for (let j = i + 1; j < n; j++) {
            if (s[i] === s[j]) {
              dp[i][j] = dp[i + 1][j - 1]
            } else {
              dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1
            }
          }
        }
        return dp[0][n - 1]
      }
      console.log(minInsertions('zzazz'))
    </script>
  </body>
</html>
